package com.leetcode.day8_3;

import java.util.Collections;

/**
 * author: the_ring
 * Time: 2021/8/3 11:34
 * log: 最短无序连续子数组
 * link:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
 */
public class Day5Code1 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,4,6,1,2,3,40,12,34};
        int result = new Solution().findUnsortedSubarray(nums);
        System.out.println(result);
    }
}

// resolve: 先对数组进行排序，然后相同位置元素是否相等
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] temp = nums.clone();
        quickSort(temp, 0, temp.length - 1);
        int left = 0, right = nums.length - 1;
        while (left < right && nums[left] == temp[left]) left++;
        if (left == right) return 0;
        while (nums[right] == temp[right]) right--;
        return right -left + 1;
    }

    public void quickSort(int[] a, int start, int end) {
        int l = start, r = end;
        if (l < r) {
            int temp = a[l];
            while (l < r) {
                while (l < r && a[r] > temp) r--;
                if (l < r) a[l++] = a[r];
                while (l < r && a[l] < temp) l++;
                if (l < r) a[r--] = a[l];
            }
            a[l] = temp;
            quickSort(a, start, l - 1);
            quickSort(a, l + 1, end);
         }
    }
}